|
In graph theory, a cut is a partition of the vertices of a graph into two disjoint subsets. Any cut determines a cut-set, the set of edges that have one endpoint in each subset of the partition. These edges are said to cross the cut. In a connected graph, each cut-set determines a unique cut, and in some cases cuts are identified with their cut-sets rather than with their vertex partitions. In a flow network, an s–t cut is a cut that requires the ''source'' and the ''sink'' to be in different subsets, and its ''cut-set'' only consists of edges going from the source's side to the sink's side. The ''capacity'' of an s–t cut is defined as the sum of capacity of each edge in the ''cut-set''. ==Definition== A cut is a partition of of a graph into two subsets ''S'' and ''T''. The cut-set of a cut is the set of edges that have one endpoint in ''S'' and the other endpoint in ''T''. If ''s'' and ''t'' are specified vertices of the graph ''G'', then an ''s''–''t'' cut is a cut in which ''s'' belongs to the set ''S'' and ''t'' belongs to the set ''T''. In an unweighted undirected graph, the ''size'' or ''weight'' of a cut is the number of edges crossing the cut. In a weighted graph, the value or weight is defined by the sum of the weights of the edges crossing the cut. A bond is a cut-set that does not have any other cut-set as a proper subset. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Cut (graph theory)」の詳細全文を読む スポンサード リンク
|